链表的排序，需要掌握的至少有两种。
我知道插入排序会比较搞笑，但还是先用插入排序试了一试，果然 TimeOut 了。感兴趣的童鞋可以来看看我在 弹指神通之链表排序 中的方法。
于是我改用了另一个基础的方案，归并排序。AC 后发现效果并不差的离谱，是 C++ 方案中的头筹呢。
简单说说归并排序。
关键在于归并，这是废话。但想要归并，显然就要有两段链表，我们的原始链表显然就应该分割为两段。我们把这个分割过程，抽取成一个函数。
void frontBackSplit(ListNode *source, ListNode **frontRef, ListNode **backRef) {
if (source == NULL || sorce->next == NULL) return;
else {
ListNode *slow = source, *fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}这里面一个基本的技巧就是快慢指针，LeetCode 里面链表题中出现过多次使用这个技巧解决的，有心的童鞋应该会心一笑。
另外，我们可以利用之前的遇到过的 019. Merge Two Sorted Lists.
这样我们的 mergeSort 函数将会无比简单。
void mergeSort(ListNode **headRef) {
ListNode *head = *headRef, *front, *back;
if (head == NULL || head->next == NULL) return;
frontBackSplit(head, &front, &back);
mergeSort(&front);
mergeSort(&back);
*headRef = sortedMerge(front, back);
}#include <cstddef>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
void moveNode(ListNode **destRef, ListNode **sourceRef) {
ListNode *newNode = *sourceRef;
*sourceRef = newNode->next;
newNode->next = *destRef;
*destRef = newNode;
}
ListNode *sortedMerge(ListNode *a, ListNode *b) {
ListNode *ret = nullptr, **lastPtrRef = &ret;
for (; a && b; lastPtrRef = &((*lastPtrRef)->next)) {
if (a->val <= b->val) moveNode(lastPtrRef, &a);
else moveNode(lastPtrRef, &b);
}
*lastPtrRef = a ? a : b;
return ret;
}
void frontBackSplit(ListNode *source, ListNode **frontRef, ListNode **backRef) {
if (source == nullptr || source->next == nullptr) {*frontRef = source; *backRef = nullptr;}
else {
ListNode *slow = source, *fast = source->next;
while (fast != nullptr) {
fast = fast->next;
if (fast != nullptr) {
slow = slow->next;
fast = fast->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = nullptr;
}
}
void mergeSort(ListNode **headRef) {
ListNode *head = *headRef, *front, *back;
if (head == nullptr || head->next == nullptr) return;
frontBackSplit(head, &front, &back);
mergeSort(&front);
mergeSort(&back);
*headRef = sortedMerge(front, back);
}
public:
ListNode *sortList(ListNode *head) {
mergeSort(&head);
return head;
}
};